#pragma once

#include <string>
#include <vector>

namespace solution_060
{

class Solution
{
public:
    std::string getPermutation(int n, int k)
    {
        --k;

        std::string num_str;
        for (int i = 1; i <= n; ++i)
            num_str.push_back('0' + i);

        std::vector<long> A_nn;
        for (long i = 1, a_nn = 1; i < n; ++i)
            A_nn.push_back(a_nn *= i);

        std::string perm_str;
        while (!A_nn.empty()) {
            auto a_nn = A_nn.back();
            auto index = k / a_nn;

            perm_str.push_back(num_str.at(index));
            num_str.erase(num_str.cbegin() + index);

            k %= a_nn;
            A_nn.pop_back();
        }
        perm_str.push_back(num_str.front());
        return perm_str;
    }
};

}  /* namespace solution_060 */

